The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Coleman’s theory of p-adic integration figures prominently in several number-theoretic applications, such as finding torsion and rational points on curves, and computing p-adic regulators in K-theory (including p-adic heights on elliptic curves). We describe an algorithm for computing Coleman integrals on hyperelliptic curves, and its implementation in Sage.
We present a variant of the Lagrange-Gauss reduction of quadratic forms designed to minimize the norm of the reduction matrix within a quadratic complexity. The matrix computed by our algorithm on the input f has norm $O(\parallel f \parallel^{1/2}/\Delta_{f}^{1/4})$ , which is the square root of the best previously known bounds using classical algorithms. This new bound allows us to fully prove...
We present improvements to the index-calculus algorithm for the computation of the ideal class group and regulator of a real quadratic field. Our improvements consist of applying the double large prime strategy, an improved structured Gaussian elimination strategy, and the use of Bernstein’s batch smoothness algorithm. We achieve a significant speed-up and are able to compute the ideal class group...
The negation map can be used to speed up the Pollard rho method to compute discrete logarithms in groups of elliptic curves over finite fields. It is well known that the random walks used by Pollard rho when combined with the negation map get trapped in fruitless cycles. We show that previously published approaches to deal with this problem are plagued by recurring cycles, and we propose effective...
The best known algorithm to compute the Jacobi symbol of two n-bit integers runs in time O(M(n)logn), using Schönhage’s fast continued fraction algorithm combined with an identity due to Gauss. We give a different O(M(n)logn) algorithm based on the binary recursive gcd algorithm of Stehlé and Zimmermann. Our implementation — which to our knowledge is the first to run in time O(M(n)logn) — is faster...
In this paper we study structures related to torsion of elliptic curves defined over number fields. The aim is to build families of elliptic curves more efficient to help factoring numbers of special form, including numbers from the Cunningham Project. We exhibit a family of curves with rational ℤ/4ℤ×ℤ/4ℤ torsion and positive rank over the field ℚ(ζ8) and a family of elliptic curves with...
Mazur proved that any element ξ of order three in the Shafarevich-Tate group of an elliptic curve E over a number field k can be made visible in an abelian surface A in the sense that ξ lies in the kernel of the natural homomorphism between the cohomology groups $H^1({\rm Gal}({\overline k}/k),E) \rightarrow H^1({\rm Gal}({\overline k}/k),A)$ . However, the abelian surface in Mazur’s construction...
For K3 surfaces, we derive some conditions the characteristic polynomial of the Frobenius on the étale cohomology must satisfy. These conditions may be used to speed up the computation of Picard numbers and the decision of the sign in the functional equation**. Our investigations are based on the Artin-Tate formula.
We adapt the CRT approach for computing Hilbert class polynomials to handle a wide range of class invariants. For suitable discriminants D, this improves its performance by a large constant factor, more than 200 in the most favourable circumstances. This has enabled record-breaking constructions of elliptic curves via the CM method, including examples with |D| > 1015.
Lattices over number fields arise from a variety of sources in algorithmic algebra and more recently cryptography. Similar to the classical case of ℤ-lattices, the choice of a nice, “short” (pseudo)-basis is important in many applications. In this article, we provide the first algorithm that computes such a “short” (pseudo)-basis. We utilize the LLL algorithm for ℤ-lattices together with the Bosma-Pohst-Cohen...
Let p be a rational prime and let Φ(X) be a monic irreducible polynomial in Z[X], with nΦ = degΦ and δΦ = vp(discΦ). In [13] Montes describes an algorithm for the decomposition of the ideal in the algebraic number field K generated by a root of Φ. A simplified version of the Montes algorithm, merely testing Φ(X) for irreducibility over Q...
We report on a computation of congruent numbers, which subject to the Birch and Swinnerton-Dyer conjecture is an accurate list up to 1012. The computation involves multiplying long theta series as per Tunnell (1983). The method, which we describe in some detail, uses a multimodular disk based technique for multiplying polynomials out-of-core which minimises expensive disk access by keeping data truncated.
Isogeny volcanoes are graphs whose vertices are elliptic curves and whose edges are ℓ-isogenies. Algorithms allowing to travel on these graphs were developed by Kohel in his thesis (1996) and later on, by Fouquet and Morain (2001). However, up to now, no method was known, to predict, before taking a step on the volcano, the direction of this step. Hence, in Kohel’s and Fouquet-Morain algorithms, we...
An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves of the same endomorphism ring, the previous best known algorithm has a worst case running time which is exponential in the length of the input. In this paper we show this problem...
This paper revisits a model for elliptic curves over ℚ introduced by Huff in 1948 to study a diophantine problem. Huff’s model readily extends over fields of odd characteristic. Every elliptic curve over such a field and containing a copy of ℤ/4ℤ ×ℤ/2ℤ is birationally equivalent to a Huff curve over the original field. This paper extends and generalizes Huff’s model. It presents fast explicit...
In this paper, we present a new approach based on theta functions to compute Weil and Tate pairings. A benefit of our method, which does not rely on the classical Miller’s algorithm, is its generality since it extends to all abelian varieties the classical Weil and Tate pairing formulas. In the case of dimension 1 and 2 abelian varieties our algorithms lead to implementations which are efficient and...
Let f(x) ∈ Z[x] be a totally real polynomial with roots α1 ≤ ... ≤ αd. The span of f(x) is defined to be αd − α1. Monic irreducible f(x) of span less than 4 are special. In this paper we give a complete classification of those small-span polynomials which arise as characteristic polynomials of integer symmetric...
We propose some kind of new attack which gives the solution of the discrete logarithm problem for the Jacobian of a curve defined over an extension field , considering the set of the union of factor basis and large primes B0 given by points of the curve whose x-coordinates lie in . In this attack, an element of the divisor group which is written by...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.